/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head)
    {
        unordered_map<Node*, Node*> map;

        Node* cur = head;
        Node* ret = new Node(0), * pre = ret;
        while (cur != nullptr)
        {
            Node* newnode = new Node(cur->val);
            newnode->random = cur->random;
            pre->next = newnode;

            pre = newnode;
            map[cur] = newnode;
            cur = cur->next;
        }
        cur = ret->next;
        while (cur != nullptr)
        {
            cur->random = map[cur->random];
            cur = cur->next;
        }
        pre = ret, ret = ret->next;
        delete pre;
        return ret;
    }
};